package algorithm.impl;

import algorithm.Sort;

import static algorithm.SortHelper.*;

/**
 * 希尔排序<br />
 * O(n^2)时间<br />
 */
public class ShellSort implements Sort {
    public <T extends Comparable> void sort(T[] arr) {

        int stepForward = 3;
        int h = 1, n = arr.length;
        while( h < n/stepForward ) {
            h = stepForward * h + 1;
            // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        }
//
//        while( h >= 1 ){
//            // h-sort the array
//            for( int i = h ; i < n ; i ++ ){
//                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
//                T e = arr[i];
//                int j;
//                for( j = i ; j >= h && less(e, arr[j-h]); j -= h )
//                    arr[j] = arr[j-h];
//                arr[j] = e;
//            }
//            h /= stepForward;
//        }
        for (; h > 0; h /= stepForward) {

            for (int count = 0; count < h; count++) {
                for (int i = count + h; i < arr.length; i += h) {
                    T e = arr[i];
                    int j;
                    for (j = i; j > count && !less(arr[j - h], e); j -= h) {
                        arr[j] = arr[j - h];
                    }
                    arr[j] = e;
                }
            }
        }

    }


    public static void main(String[] args) {

        ShellSort sort = new ShellSort();
        Integer[] integers = new Integer[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        testSort("选择排序", sort, integers);

        Integer[] integers2 = new Integer[]{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        testSort("选择排序", sort, integers2);
        System.out.println("----------------------");
        Integer[] integers3 = new Integer[]{6, 5, 4, 3, 2, 1};
        testSort("选择排序", sort, integers3);

        Float[] floats = new Float[]{4.4f, 3.3f, 2.2f, 1.1f, 0.0f};
        testSort("选择排序", sort, floats);

        Character[] characters = new Character[]{'z', 'y', 'x', 'w', 'v', 'u'};
        testSort("选择排序", sort, characters);

        String[] strings = new String[]{"E", "D", "C", "B", "A"};
        testSort("选择排序", sort, strings);

        int n = 100000;
        Integer[] array = generateRandomArray(n, 0, n);
        testSort("选择排序", sort, array);

        //近似排序的情况下, 速度很快
        array = generateNearlyOrderedArray(n, n / 10);
        testSort("选择排序", sort, array);

    }
}
